package linkedlist;



/**
 * 带头指针和头结点的单链表
 */
public class LinkedList<T> implements LList<T> {
    public Node<T> head;
    private int len = 0;

    /*
     * 构造空单链表
     */
    public LinkedList() {
        this.head = new Node<T>(); // 创建头结点，data和next值均为null
    }

    /**
     * 尾插法建表
     */
    public LinkedList(T[] element) {
        this(); // 创建空单链表，只有头结点
        Node<T> rear = this.head; // rear指向单链表最后一个结点
        // 若element==null，抛出空对象异常

        // element.length==0时，构造空链表
        for (int i = 0; i < element.length; i++) {
            rear.next = new Node<T>(element[i], null); // 尾插入,创建结点链入rear结点之后
            rear = rear.next; // rear指向新的链尾结点
            len++;
        }
    }

    /**
     * 判断单链表是否为空
     */
    public boolean isEmpty() {
        return this.head.next == null;
    }

    /**
     * 返回单链表长度，O(n)
     */
    public int length() {
        int i = 0;
        Node<T> p = this.head.next; // p从单链表第一个结点开始
        while (p != null) // 若单链表未结束
        {
            i++;
            p = p.next; // p到达后继结点
        }
        return i;
    }

    /**
     * 返回单链表所有元素的描述字符串，形式为“(,)”， 覆盖Object类的toString()方法，O(n)
     */
    public String toString() {
        String str = "(";
        for (Node<T> p = this.head.next; p != null; p = p.next) {
            str += p.data.toString();
            if (p.next != null)
                str += ", "; // 不是最后一个结点时后加分隔符
        }
        return str + ")"; // 空表返回()
    }

    /**
     * 查找操作 返回第i（≥0）个元素，若i<0或大于表长则返回null，O(n)
     */
    public T get(int i) {
        if (i >= 0) {
            Node<T> p = this.head.next;
            for (int j = 0; p != null && j < i; j++)
                p = p.next;
            if (p != null)
                return p.data; // p指向第i个结点
        }
        return null; // 当i<0或大于表长时
    }

    /**
     * 设置第i（≥0）个元素值为x。若i<0或大于表长则抛出序号越界异常；若x==null，不操作。O(n)
     */
    public void set(int i, T x) {
        if (x == null)
            return; // 不能设置元素为空对象
        Node<T> p = this.head.next;
        for (int j = 0; p != null && j < i; j++)
            p = p.next;
        if (i >= 0 && p != null)
            p.data = x; // p指向第i个结点
        else
            throw new IndexOutOfBoundsException(i + ""); // 抛出序号越界异常
    }

    /**
     * 插入第i（≥0）个元素值为x。 若x==null，不插入。
     * 若i<0，插入x作为第0个元素； 若i大于表长，插入x作为最后一个元素。O(n)
     * 可用于尾插法建表
     */
    public void insert(int i, T x) {
        if (x == null)  // 不能插入空对象
            return;
        Node<T> p = this.head; // p指向头结点
        for (int j = 0; p.next != null && j < i; j++) { // 寻找插入位置
            p = p.next;
        }
        p.next = new Node<T>(x, p.next);
        len++;
    }

    public void append(T x) // 在单链表最后添加x对象，O(n)
    {
        insert(Integer.MAX_VALUE, x); // 遍历一次
        // insert(this.length(), x); //需遍历单链表两次，效率较低
        // this.insertAfter(this.getLast(),x)!=null; //遍历一次
    }

    /**
     * 删除第i（≥0）个元素，返回被删除对象。
     * 若i<0或i大于表长，不删除，返回null。
     * O(n)
     */
    public T remove(int i) {
        if (i >= 0 && i < length()) {
            Node<T> p = this.head;
            // 定位到待删除结点（i）的前驱结点（i-1）
            for (int j = 0; p.next != null && j < i; j++) {

                p = p.next;
            }
            if (p.next != null) {
                T old = p.next.data; // 获得原对象
                p.next = p.next.next; // 删除p的后继结点
//                System.out.println("node-" + i + ":" + old + ",delete");
                len--;
                return old;
            }
        }
//        System.out.println("node-" + i + ":not exist...!");
        // 当i<0或大于表长时
        return null;
    }

    public void removeAll() // 删除单链表所有元素
    {
        this.head.next = null; // Java将自动收回各结点所占用的内存空间
        len = 0;
    }

    /**
     * 按结点值查找
     */
    @Override
    public int search(T key) {
        if (key == null)
            return -1;
        int position = 0;
        for (Node<T> p = this.head.next; p != null; p = p.next) {
            position++;
            if (p.data.equals(key))
                return position;
        }
        return -1;
    }



    /**
     * 判断线性表是否包含关键字为key元素
     */
    @Override
    public boolean contain(T key) {
        return this.search(key) != -1; // 以查找结果获得判断结果
    }

    @Override
    public void showListInfo() {
        System.out.println("linkedlist:" + this.toString() + ", length=" + this.length());
    }

}
